[[분류:정보]]
== 개요 ==
선택 알고리즘(Selection Algorithm)은 정렬되지 않은 리스트에서 k번째로 작은(또는 큰) 원소를 찾는 알고리즘이다. 리스트 전체를 정렬하면 [math(\Theta(n \log n))]이 걸리지만, 이 알고리즘들을 이용하면 평균적으로 [math(\Theta(n))] 내에 해결이 가능하다.
== 퀵 선택(Quick Select) ==
퀵 정렬의 분할(Partition) 로직을 활용하여 탐색 범위를 좁혀나가는 방식이다.
=== 작동 단계 ===
리스트에서 하나의 피벗(Pivot)을 선택한다.
피벗보다 작은 원소는 왼쪽, 큰 원소는 오른쪽으로 보낸다(Partition).
피벗이 놓인 위치가 찾고자 하는 k번째라면 해당 값을 반환한다.
k가 피벗의 위치보다 작으면 왼쪽 구역만, 크면 오른쪽 구역만 선택하여 위 과정을 재귀적으로 반복한다.
=== 의사 코드 ===
{{{#!syntax java
quickSelect(A[], p, r, k):
if (p == r)
return A[p]
q ← partition(A, p, r)
i ← q - p + 1
if (k == i)
return A[q]
else if (k < i)
return quickSelect(A, p, q - 1, k)
else
return quickSelect(A, q + 1, r, k - i)
}}}
== 선형 시간 선택(Linear Time Selection) ==
퀵 선택의 최악의 경우([math(\Theta(n^2))])를 해결하기 위해 '중앙값들의 중앙값'을 피벗으로 사용하는 방식이다.
=== 작동 단계 ===
그룹화: 원소들을 5개씩 묶어 그룹을 만든다.
각 그룹의 중앙값: 각 5개짜리 그룹 내에서 중앙값을 찾는다.
중앙값들의 중앙값(M): 단계 2에서 구한 중앙값들을 모아 다시 그들의 중앙값 M을 찾는다.
분할: M을 피벗으로 삼아 전체 리스트를 분할한다.
재귀: 분할된 위치에 따라 k번째 원소가 있는 구역으로 이동하여 과정을 반복한다.
=== 의사 코드 ===
{{{#!syntax java
linearTimeSelect(A[], p, r, k):
if (r - p + 1 <= 5)
A[p...r]을 정렬하여 k번째 원소를 반환한다.
// 그룹별 중앙값 구하기
for i ← 0 to ⌈(r - p + 1) / 5⌉ - 1
B[i] ← 5개 원소 그룹 중 중앙값
// 중앙값들의 중앙값 M 구하기
M ← linearTimeSelect(B, 0, ⌈(r - p + 1) / 5⌉ - 1, ⌈(r - p + 1) / 10⌉)
q ← partitionWithPivot(A, p, r, M)
i ← q - p + 1
if (k == i)
return A[q]
else if (k < i)
return linearTimeSelect(A, p, q - 1, k)
else
return linearTimeSelect(A, q + 1, r, k - i)
}}}
== 성능 분석 ==
퀵 선택: 평균 [math(\Theta(n))], 최악 [math(\Theta(n^2))]
선형 시간 선택: 모든 경우 [math(\Theta(n))]
